翻訳と辞書 Words near each other ・ Fractal derivative ・ Fractal Design ・ Fractal dimension ・ Fractal dimension on networks ・ Fractal flame ・ Fractal Glider ・ Fractal globule ・ Fractal in soil mechanics ・ Fractal lake ・ Fractal landscape ・ Fractal Notes and Shoe Throats ・ Fractal Possession ・ Fractal Records ・ Fractal sequence ・ Fractal transform ・ Fractal tree index ・ Fractal-generating software ・ Fractale ・ Fractalgrid ・ Fractals (journal) ・ Fractint ・ Fractio Panis ・ Fractio panis (liturgy) ・ Fraction ・ Fraction (chemistry) ・ Fraction (comics) ・ Fraction (mathematics) ・ Fraction (religion) ・ Fraction anthem ・ Fraction Bars Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fractal tree index ： ウィキペディア英語版 Fractal tree index In computer science, a Fractal Tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a Fractal Tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a Fractal Tree index has buffers at each node, which allow insertions, deletions and other changes to be stored in intermediate locations. The goal of the buffers is to schedule disk writes so that each write performs a large amount of useful work, thereby avoiding the worst-case performance of B-trees, in which each disk write may change a small amount of data on disk. Like a B-tree, Fractal Tree indexes are optimized for systems that read and write large blocks of data. The Fractal Tree index has been commercialized in databases by Tokutek. Originally, it was implemented as a cache-oblivious lookahead array, but the current implementation is an extension of the B''ε'' tree. The B''ε'' is related to the Buffered Repository Tree. The Buffered Repository Tree has degree 2, whereas the B''ε'' tree has degree B''ε''. The Fractal Tree index has also been used in a prototype filesystem. An open source implementation of the Fractal Tree index is available,〔(Github Repository )〕 which demonstrates the implementation details outlined below. == Overview == In Fractal Tree indexes, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Each internal node of a B-tree will contain a number of keys that is one less than its branching factor. The keys act as separation values which divide its subtrees. Keys in subtrees are stored in search tree order, that is, all keys in a subtree are between the two bracketing values. In this regard, they are just like B-trees. Fractal Tree indexes and B-trees both exploit the fact that when a node is fetched from storage, a block of memory, whose size is denoted by $B$, is fetched. Thus, nodes are tuned to be of size approximately $B$. Since access to storage can dominate the running time of a data structure, the time-complexity of external memory algorithms is dominated by the number of read/writes a data structure induces. (See, e.g.,〔 〕 for the following analyses.) In a B-tree, this means that the number of keys in a node is targeted to be enough to fill the node, with some variability for node splits and merges. For the purposes of theoretical analysis, if $O(B)$ keys fit in a node, then the tree has depth $O(\backslash log\_B\; N)$, and this is the I/O complexity of both searches and insertions. Fractal Trees nodes use a smaller branching factor, say, of $\backslash sqrt$. The depth of the tree is then $O(\backslash log\_\backslash sqrt\; N)\; =\; O(\backslash log\_B\; N)$, thereby matching the B-tree asymptotically. The remaining space in each node is used to buffer insertions, deletion and updates, which we refer to in aggregate as messages. When a buffer is full, it is flushed to the children in bulk. There are several choices for how the buffers are flushed, all leading to similar I/O complexity. Each message in a node buffer will be flushed to a particular child, as determined by its key. Suppose, for concreteness, that messages are flushed that are heading to the same child, and that among the $\backslash sqrt+1$ children, we pick the one with the most messages. Then there are at least $\backslash frac\; B\; \backslash approx\; \backslash sqrt$ messages that can be flushed to the child. Each flush requires $O(1)$ flushes, and therefore the per-message cost of a flush is $O\backslash left(\backslash frac\; 1\; \backslash sqrt\backslash right)$. Consider the cost of an insertion. Each message gets flushed $O(\backslash log\_B\; N)$ times, and the cost of a flush is $O\backslash left(\backslash frac\; 1\; \backslash sqrt\backslash right)$. Therefore, the cost of an insertion is $O\backslash left(\backslash frac\; \backslash sqrt\backslash right)$. Finally, note that the branching factor can vary, but for any branching factor $B^$, the cost of a flush is $O\backslash left(\backslash frac\; 1\; \{B^\{1-\backslash varepsilon\}\}\backslash right)$, thereby providing a smooth tradeoff between search cost, which depends on the depth of the search tree, and therefore the branching factor, versus the insertion time, which depends on the depth of the tree but more sensitively on the size of the buffer flushes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fractal tree index」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.